package com.nowcoder.study;


import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;

/**
 * DFS查找图中的环
 */
public class FindThePath {


    public class Point {
        int x;
        int y;

        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
    }


    boolean[] visted;
    int[] uf ;

    int n;

    public String solve(int[] param, Point[] edge) {
        n = param[0];
        uf = new int[n+1];
        visted = new boolean[n+1];
        for(Point p : edge){
            uf[p.x] = p.y;
            uf[p.y] = p.x;
        }

        return dfs(1,1) ? "Yes" : "No";

    }


    public boolean dfs(int x, int y){
        for(int i=0; i<n; i++){
            if(i == y) continue;
            if(i == 1) return true;
            if(visted[i]) continue;
            visted[i] = true;
            if(dfs(i,x)) return true;
        }
        return false;
    }

    @Test
    public void test(){
        int[] param = {4,4};
        Point p1 = new Point(1,2);
        Point p2 = new Point(2,3);
        Point p3 = new Point(3,4);
        Point p4 = new Point(4,2);
        Point[] edge = {p1,p2,p3,p4};

        System.out.println(solve(param,edge));
    }


}
